import java.util.Arrays;
import java.util.List;

public class _315 {
    //归并排序思路
    static class Solution {
        public List<Integer> countSmaller(int[] nums) {
            //归并排序，分区时， L,R ,R指针移动，L 索引处数量增加.
            int[][] tuples = new int[nums.length][3];//0，1，2处分别存id,num,count
            for (int i = 0; i < nums.length; i++) {
                tuples[i] = new int[]{i, nums[i], 0};
            }
            mergeSort(tuples, 0, tuples.length - 1);
            Integer[] res = new Integer[nums.length];
            for (int[] tuple : tuples) {
                res[tuple[0]] = tuple[2];
            }
            return Arrays.asList(res);
        }

        //[i,j-1],[j,k];
        public void merge(int[][] arr, int i, int j, int k) {
            int[][] L = new int[j - i][3];
            int[][] R = new int[k - j + 1][3];
            System.arraycopy(arr, i, L, 0, L.length);
            System.arraycopy(arr, j, R, 0, R.length);
            int x = 0;
            int y = 0;
            int z = i;
            while (x < L.length && y < R.length) {
                if (L[x][1] <= R[y][1]) {
                    L[x][2] += y; //核心，当左侧不比右侧大，直接加上右侧已经放入原数组的数量
                    arr[z++] = L[x++];
                } else {
                    arr[z++] = R[y++];
                }
            }
            while (x < L.length) {
                L[x][2] += y;
                arr[z++] = L[x++];
            }
            while (y < R.length) {
                arr[z++] = R[y++];
            }
        }

        public void mergeSort(int[][] A, int l, int r) {
            if (l >= r) return;
            int mid = l + (r - l) / 2;
            mergeSort(A, l, mid);
            mergeSort(A, mid + 1, r);
            merge(A, l, mid + 1, r);
        }
    }

    static class Solution2{
        //排名第一的思路，暂时没明白
        public List<Integer> countSmaller(int[] nums) {
            int sz = 20002;
            int n = nums.length;
            int[] ft = new int[20002];
            Integer[] res = new Integer[n];
            int j,tmp;

            for (int i=n-1; i>=0; i--) {
                j = nums[i] + 10000;
                tmp = 0;
                while(j>0) {
                    tmp += ft[j];
                    j -= (j&-j);
                }
                res[i] = tmp;
                j = nums[i] + 10001;
                while(j<20002) {
                    ft[j]++;
                    j += (j&-j);
                }
            }
            return Arrays.asList(res);
        }
    }
}
